package com.zx._12_算法.剑指offer._2022;

import java.util.Arrays;

public class 最小的k个数 {

    /**
     * 1.利用工具
     *
     * @param arr
     * @param k
     * @return
     */
    public int[] getLeastNumbers1(int[] arr, int k) {
        int[] vec = new int[k];
        Arrays.sort(arr);
        for (int i = 0; i < k; ++i) {
            vec[i] = arr[i];
        }
        return vec;
    }

    /**
     * 2. 快速排序
     *
     * @param arr
     * @param k
     * @return
     */
    public int[] getLeastNumbers2(int[] arr, int k) {
        sort(arr, 0, arr.length - 1, k);
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public void sort(int[] arr, int begin, int end, int k) {
        int left = begin;
        int right = end;
        while (left < right) {
            int base = arr[left];

            while (left < right && arr[right] >= base) {
                right--;
            }
            if (arr[right] < base) {
                swap(arr, right, left);
            }
            while (left < right && arr[left] <= base) {
                left++;
            }
            if (arr[left] > base) {
                swap(arr, right, left);
            }
        }
        if (left == k) {
            return;
        }
        if (begin < left) {
            sort(arr, begin, left - 1, k);
        }
        if (right < end) {
            sort(arr, right + 1, end, k);
        }
    }


    /**
     * 3. 堆排序
     *
     * @param arr
     * @param k
     * @return
     */
    public int[] getLeastNumbers(int[] arr, int k) {
        // 构建最小对
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        int[] res = new int[k];
        int idx = 0;
        for (int i = arr.length - 1; i >= arr.length - k; i--) {
            swap(arr, 0, i);
            adjustHeap(arr, 0, i);
            res[idx] = arr[i];
            idx++;
        }
        return res;
    }

    private void adjustHeap(int[] nums, int i, int len) {
        int temp = nums[i];
        for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
            int left = k;
            int right = k + 1;

            // 1.比较左右叶子节点，k=最大的叶子节点
            if (right < len && nums[right] < nums[left]) {
                k = right;
            }
            // 2.比较最大的叶子节点与非叶子节点
            if (temp > nums[k]) {
                nums[i] = nums[k];
                nums[k] = temp;
                i = k;
            } else {
                break;
            }
        }
    }

    public void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

}
